Exercici 9 (Tasca 6).
(R (decidable/recursive languages),
RE (semi-decidable/ recursively enumerable languages))
Són funcions (computables)?
Un conjunt S \subseteq \mathbb{N} \times \mathbb{N} s’identifica amb el graf d’una funció (parcial) si sempre que (x,y) \in S i (x,z) \in S, es compleix que y = z. Quins dels subconjunts següents de \mathbb{N} \times \mathbb{N} són el graf d’una funció? Són les funcions computables?
Una relació R sobre \mathbb{N} (és a dir, un conjunt R \subseteq \mathbb{N} \times \mathbb{N}) és una funció (parcial) si sempre que (x,y)\in R i (x,z)\in R, es compleix y=z. Quines de les relacions següents sobre \mathbb{N} són funcions? Són les funcions computables?
- \{ (x,y) \mid M_x(x)=y\}.
- \{ (x,y) \mid M_x(x) \leq y\}.
- \{ (x,y) \mid M_x(x) \geq y\}.
- \{ (x,y) \mid M_x(x) = M_y(y)\}.
- \{ (x,y) \mid M_x(x) \text{ s'atura en } y \text{ passos o més}\}.
- \{ (x,y) \mid M_x(x) \text{ s'atura en exactament } y \text{ passos}\}.
- \{ (x,y) \mid M_x(x)\!\downarrow\} \cup \{ (x,y) \mid M_x(x)\!\uparrow\}.
- \{ (x,y) \mid M_x(x)\!\downarrow\}.
- \{ (x,y) \mid M_x(x)\!\uparrow\}.
- \{ (x,y) \mid y = \lvert\{z \mid M_x(z)\!\downarrow\}\rvert\}.